'''
难度 简单
标签 二分查找
题目链接 https://leetcode.cn/problems/sqrtx/description/
'''


class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        头,尾,结果 = 0, x, -1

        while 头 <= 尾:
            # 不写 中 = (头 + 尾) // 2 原因：头+尾 有溢出的可能
            中 = 头 + (尾 - 头) // 2
            # 不写 x < 中 * 中 也是避免溢出
            if x / 中 < 中:
                尾 = 中 - 1
            else:
                结果 = 中
                头 = 中 + 1

        return 结果

if __name__ == '__main__':
    s = Solution()
    参数 = [
        [4],
        [8],
    ]
    预期 = [
        2,
        2,
    ]
    for k,v in enumerate(参数):
        r = s.mySqrt(v[0])
        if r != 预期[k]:
            print("第{}个case不通过 期望={} 结果={}\n".format(
                k+1,
                预期[k],
                r
            ))